//
// Created by dengspc on 2019/1/10.
//

#ifndef INC_010_ALGORITHM_QUICKSORT_H
#define INC_010_ALGORITHM_QUICKSORT_H

#include <iostream>
#include <algorithm>
#include "TestSortHelper.h"
#include "InsertSort.h"

using namespace std;

//对 arr分割 [l,r]排序
template <typename T>
int* __partition3(T arr[], int l, int r) {
    swap(arr[l], arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int lt = l;
    int gt = r+1;
    int i = l + 1;

    while (i < gt) {
        if (arr[i] > v) {
            swap(arr[gt - 1], arr[i]);
            gt--;
        }
        else if (arr[i] < v) {
            swap(arr[lt + 1], arr[i]);
            lt++;
            i++;
        }
        else {
            i++;
        }
    }
    swap(arr[l], arr[lt]);
    static int n[2];
    n[0] = lt - 1;
    n[1] = gt;
    return n;
}


template <typename T>
int __partition2(T arr[], int l, int r){

    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    T v = arr[l];

    // arr[l+1...i) <= v; arr(j...r] >= v
    int i = l+1, j = r;
    while( true ){
        while( i <= r && arr[i] < v )
            i ++;

        while( j >= l+1 && arr[j] > v )
            j --;

        if( i > j )
            break;

        swap( arr[i] , arr[j] );
        i ++;
        j --;
    }

    swap( arr[l] , arr[j]);
    return j;
}
//对 arr分割 [l,r]排序
template <typename T>
int __partition1(T arr[], int l, int r) {
    swap(arr[l],arr[rand() % (r - l + 1) + l]);

    T v = arr[l];

    int j = l;
    for (int i = l + 1;i <= r;i++) {
        if (arr[i] < v) {
            swap(arr[++j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);
    return j;

}

//对 arr分割 [l,r]排序
template <typename T>
int __partition(T arr[], int l, int r) {
    T v = arr[l];

    int j = l;
    for (int i = l + 1;i <= r;i++) {
        if (arr[i] < v) {
            swap(arr[++j], arr[i]);
        }
    }
    swap(arr[l], arr[j]);
    return j;

}


//对 __quickSort [l,r]排序
template <typename T>
void __quickSort(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }

    int j = __partition(arr, l, r);
    __quickSort(arr, l, j);
    __quickSort(arr, j+1, r);

}

//对 __quickSort [l,r]排序
template <typename T>
void __quickSort1(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }
    int j = __partition1(arr, l, r);
    __quickSort1(arr, l, j);
    __quickSort1(arr, j+1, r);

}
//对 __quickSort [l,r]排序
template <typename T>
void __quickSort2(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }
    int j = __partition2(arr, l, r);
    __quickSort2(arr, l, j);
    __quickSort2(arr, j+1, r);

}

//对 __quickSort [l,r]排序
template <typename T>
void __quickSort3(T arr[], int l, int r) {
    if (r - l <= 15) {
        insertSort(arr, l, r);
        return;
    }
    int *j = __partition3(arr, l, r);
    __quickSort3(arr, l, j[0]);
    __quickSort3(arr, j[1], r);
    delete[] j;

}


template <typename T>
void quickSort(T arr[], int n) {
    srand(time(NULL));
    __quickSort(arr, 0, n - 1);
}

template <typename T>
void quickSort1(T arr[], int n) {
    srand(time(NULL));
    __quickSort1(arr, 0, n - 1);
}

template <typename T>
void quickSort2(T arr[], int n) {
    srand(time(NULL));
    __quickSort2(arr, 0, n - 1);
}

template <typename T>
void quickSort3(T arr[], int n) {
    srand(time(NULL));
    __quickSort3(arr, 0, n - 1);
}

#endif //INC_010_ALGORITHM_QUICKSORT_H
